from collections import deque
from typing import List


class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        number_2_pos = {}
        grid = [[j + 1 for j in range(i * n, i * n + n)] for i in range(n)]
        grid.reverse()
        for i in range(n - 2, -1, -2):
            grid[i].reverse()
        for i in range(n):
            for j in range(n):
                number_2_pos[grid[i][j]] = (i, j)
        queue = deque([(n - 1, 0, 0)])  # i,j,distance
        visited = set()
        while queue:
            cx, cy, cd = queue.popleft()
            idx = grid[cx][cy]  # 编号
            if idx == n ** 2:
                return cd
            for nidx in range(idx + 1, min(idx + 7, n ** 2 + 1)):
                if nidx in visited: continue
                visited.add(nidx)
                nx, ny = number_2_pos[nidx]
                if board[nx][ny] != -1:
                    nx, ny = number_2_pos[board[nx][ny]]
                    if nidx == n ** 2: return -1
                queue.append((nx, ny, cd + 1))
        return -1


if __name__ == "__main__":
    s = Solution()
    r = s.snakesAndLadders([[1, 1, -1], [1, 1, 1], [-1, 1, 1]])
    print(r)
